package io.rong.util;

public class SortUtil {
	
	/**o(n2) 稳定
	 * 插入排序 思路上从待排序的数据中选出一个，插入到前面合适的位置
	 * @Description: TODO
	 * @param @param s
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] insertSort(int[] s) {
		for (int i = 0; i < s.length; i++) {
			int j = i - 1;// 去先下标
			int temp = s[i];
			if (j > 0 && s[j]>temp) {// 如果小于就让数据往后面移动
				s[j + 1] = s[j];
				j--;
			}
			s[j + 1] = temp;// 插入位置
		}
		return s;
	}
	/**o(n2) 不稳定
	 * 通过循环，找出最小的数的下标，赋值于k，即k永远保持待排序数据中最小的数的下标，最后和当前位置i互换数据即可。
	 * @Description: TODO
	 * @param @param s
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] selectSort(int[] s) {
		int i,j,k,temp;//k 为最小数下标 
		for ( i = 0; i < s.length-1; i++) {
			k=i;
			for ( j = i+1; j < s.length; j++) {
				if(s[j]<s[k]){
					k=j;
				}
			}
			if(i!=k){
				temp = s[i];
				s[i]=s[k];
				s[k]=temp;
			}
		}
		return s;
	}
	
	
	public static int partition(int[] data, int low, int hight) {
		int key = data[low];
		while (low < hight) {
			while (low < hight && data[hight] >= key) {
				hight--;
			}
			data[low] = data[hight];
			while (low < hight && data[low] <= key) {
				low++;
			}
			data[hight]=data[low];
		}
		data[low]=key;
		return low;
	}
	/**
	 * o(nlogn) 不稳定 适合无序排序
	 * @Description: TODO
	 * @param @param s
	 * @param @param low
	 * @param @param hight
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] QuickSort( int[] s,int low,int hight){
		if(low<hight){
			int result = partition(s, low, hight);
			QuickSort(s, result+1, hight);
			QuickSort(s, low, result-1);
		}
		return s;
	}
	
	/**
	 * 冒泡排序（稳定、基本有序可达O(n)，最坏情况为O(n2)）
	 * @Description: TODO
	 * @param @param s
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] bubbletSort( int[] s){
		int temp =0;
		for (int i = 0; i < s.length; i++) {
			for (int j = s.length-1; j >i ; j--) {
				if(s[j]<s[j-1]){
					temp = s[j-1];
					s[j-1]=s[j];
					s[j]=temp;
				}
			}
		}
		return s;
	}
	/**
	 * 
	 * 
	 * @Description: TODO
	 * @param @param a 数组有序
	 * @param @param n a长度
	 * @param @param b 数组有序
	 * @param @param m b长度
	 * @param @param c 最终输出的数组 n+m
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] mergeArraySort(int[] a,int n,int[] b,int m,int[] c){
		int i=0,j=0,k=0;
		while(i<n&&j<m){
			if(a[i]<b[j]){
				c[k++]=a[i++];
			}else{
				c[k++]=b[j++];
			}
			
		}
		while(i<n){
			c[k++]=a[i++];
		}
		while(j<m){
			c[k++]=b[i++];
		}
		return c;
	}
	/**
	 * 归并排序 
	 * @Description: TODO
	 * @param @param data
	 * @param @param start
	 * @param @param end
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] mergeSort(int data[],int start,int end){
		if(end>start){
		int pos = (start+end)/2;
		mergeSort(data, start, pos);
		mergeSort(data, pos+1, end);
		merge(data, start, pos, end);
		}
		return data;
	}
	/**
	 * 归并排序子函数
	 * @Description: TODO
	 * @param @param data
	 * @param @param start
	 * @param @param pos
	 * @param @param end
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[]  merge(int data[],int start,int pos ,int end){
		int len1 = pos-start+1;//第一个数组长度
		int len2 = end-pos;//第二个数组长度
		int A[] = new int[len1+1];
		int B[] = new int[len2+1];
		for (int i = 0; i < len1; i++) {//赋值给数组
			A[i]=data[i+start-1];
		}
		A[len1]=Integer.MAX_VALUE;//设置最大数结尾标注
		for (int j = 0; j < len2; j++) {
			B[j]=data[j+pos];
		}
		B[len2]=Integer.MAX_VALUE;
		int n=0,m=0;
		for (int k = start-1; k < end; k++) {
			if(A[n]<B[m]){
				data[k]=A[n];
				n++;
			}else{
				data[k]=B[m];
				m++;
			}
		}
		return data;
	}
	/**
	 * shell 排序 不稳定 O（nlogn）
	 * @Description: TODO
	 * @param @param data
	 * @param @param n 数组长度
	 * @param @return   
	 * @return int[]  
	 * @throws
	 * @author yyf
	 * @date 2015年10月11日
	 */
	public static int[] shellSort(int[] data,int n){
		int gap= 0,i,j,temp;
		while(gap<=n){
			gap=gap*3+1;
		}
		while(gap>0){
			for(i=gap;i<n;i++){
				temp = data[i];
				j=i-gap;
				while((j>=0)&&(data[j]>temp)){
					data[j+gap]=data[j];
					j=j-gap;
				}
				data[j+gap]= temp;
			}
			gap=(gap-1)/3;
			
		}
		return data;
	}
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] sorts = new int[] { 9, 2, 7, 3, 34,43, 5  };
//		int s[] =shellSort(sorts,sorts.length);
		int s[] =bubbletSort(sorts);
		for (int i = 0; i < s.length; i++) {
			System.out.println(s[i]);
		}
	}
	
	
}
